package com.data_structure_algorithm.algorithm;

import java.util.Arrays;

/**
 * @Authror PABLO
 * @Date 2022/4/4 21:47
 * @Desc 斐波那契查找算法
 */
public class Fibonacci {

    //20位的斐波那契数列
    static int fibonacciMaxValue = 20;

    public static void main(String[] args) {

        int[] arr = {2, 5, 8, 34, 56, 234, 567, 5676, 67876};
        int valIndex = getValIndex(arr, 67876);
        System.out.println("对应下标为" + valIndex);


    }

    public static int getValIndex(int[] arr, int value) {
        if (arr.length == 0) return -1;

        int left = 0;
        int right = arr.length - 1;
        //斐波那契数列中的下标值 ,mid = left +F(k-1) -1
        int k = 0;
        int mid = 0;
        //获取斐波那契
        int[] fibonacci = getFibonacci();


        //背景：原数组的个数不一定==斐波那契数列中的某个值，那么需要找出斐波那契中正好>原数组个数的数值
        //如原数组长度==8，斐波那契中对应的 最近的 大于原数组长度 的数值是12
        //操作：原数组索引个数和斐波那契下标对应的值比较
        //目的：找到原数组个数和斐波那契数列中的最接近的数列值

        //这里-1是因为斐波那契的是具体值，代表原数组中的需要扩容的个数而不是索引，个数-1为索引
        while (right > fibonacci[k] - 1) {
            //1 1 2 3 5 8 13
            //1次 fibonacci[k] - 1 = 0  k==0
            //2次  fibonacci[k] - 1 = 0  k==1
            //3次  fibonacci[k] - 1 = 1  k==2
            //4次   fibonacci[k] - 1 = 2 k==3
            //5次   fibonacci[k] - 1 = 4 k==4
            //6次   fibonacci[k] - 1 = 7 k==5
            //7次   fibonacci[k] - 1 = 12  k==6后（值为12）不满足，right==8，

            //k下标对应的斐波那契数列值，是原数组需要扩容的范围
            k++;//斐波那契索引后移,k == 6时退出循环，对应斐波那契数字为13，13-1 = 12
        }
        //斐波那契给出的数字fibonacci[k]-1是12，但是原数组只有8，需要原数组扩容，符合斐波那契数列
        int[] temp = Arrays.copyOf(arr, fibonacci[k]); //如果原数组索引是8（个数是9），新长度是12（个数13），原数组个数+4


        //将temp数组多余部分均填充原数组的末尾值
        for (int i = right + 1; i < temp.length; i++) {
            temp[i] = arr[right];
        }
        System.out.println(right);
        //开始查找，right还是原数组长度
        while (left <= right) {
            //中间值如哦
            mid = left + fibonacci[k - 1] - 1;
            if (value < temp[mid]) {
                //待查找的值在左边
                right = mid - 1;
                //将斐波那契下标值左移，在f[k-1]的位置没找到，就在f[k-2]的地方查找
                //f[k]=f[k-1]+f[k-2]  mid左边是f[k-1]，右边是f[k-2]
                //即下次循环定位mid值
                k--;

            } else if (value > temp[mid]) {//数组右侧寻找
                left = mid + 1;
                //f[k]=f[k-1]+f[k-2]  mid左边是f[k-1]，右边是f[k-2]
                k -= 2;

            } else { //value == temp[mid]
                //谁小返回谁之前数组后面有填充，并且填充的都是数组最后的数字
                //如果mid <= right
                // 如mid == right，说明正好原数组最后一个值
                //如mid < right 说明mid对应的值在原数组内，是正常的数组值

                if (mid <= right) return mid;
                //如mid>right 说明mid对应的值在原数组外，即填充数组，因为是有序数组，超出right的部分都是right的值
                else return right;
            }


            System.out.println(mid);
        }
        System.out.println(Arrays.toString(temp));
        return -1;

    }


    //获得斐波那契数列
    public static int[] getFibonacci() {

        int[] result = new int[fibonacciMaxValue];
        result[0] = 1;
        result[1] = 1;
        for (int i = 2; i < result.length; i++) {
            result[i] = result[i - 1] + result[i - 2];
        }
        return result;

    }


}
